class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for(auto& e : wordDict)hash.insert(e);

        int n=s.size();
        vector<bool> dp(n+1);
        dp[0]=true;
        s=' '+s;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                if(dp[j-1] && hash.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
    
};
